1. Field of the Invention
The present invention is directed to a coding method of an image data, particularly to a compression/extension method including discrete cosine transform and quantization of data.
2. Description of the Background Art
FIG. 8 is a block diagram illustrating an image encoding/decoding processing. An original image data is processed in a block of N.times.N pixels, for example, a block of 8.times.8 pixels. The pixels are preprocessed in a predetermined way in a preprocess unit 91, and are encoded by an encoder 100. Then, the compressed image data is transmitted through a transmission path 300.
The compressed image data carried through the transmission path 300 is decoded by a decoder 200, and is postprocessed in a predetermined way in a postprocess unit 92 to form a restored image data of 8.times.8 pixels.
The encoder 100 comprises a discrete cosine transform (DCT) unit 101, a quantization unit 102, and an encoding unit 103. The preprocessed original image data is processed by DCT in the DCT unit 101, is quantized in the quantization unit 102 according to a quantization table 301, and is encoded by entropy coding in the encoding unit 103 according to a coding table 302 while scanned in a predetermined order.
In the entropy coding, coding based on zero run length has been well known. Thus, in order to have a longer sequence of zeroes in data to be coded (quantized data), the quantized data is zigzag scanned in order of its frequency in the DCT operations from low to high.
The decoder 200 comprises an inverse discrete cosine transform (IDCT) unit 201, an inverse quantization unit 202, and a decoding unit 203. The compressed image data is decoded in the decoding unit 203 according to the coding table 302 while scanned in a predetermined order, is inversely quantized in the inverse quantization unit 202 according to the quantization table 301, and is processed by IDCT in the IDCT unit 201.
Such encoding and decoding technique has been applied to a typical image processing method such as JPEG as a standard for compressing information of a color static image and MPEG1 as a standard for coding a dynamic image.
In the JPEG, for example, a two-dimensional DCT is practiced on the original image data of 8.times.8 pixels as described above. Suppose that a pixel value in the xth row and the yth column of the preprocessed original image data of 8.times.8 pixels is expressed as f(x, y), the two-dimensional DCT derives 8.times.8 transform values F(u, v) as follows: ##EQU1## where x, y, u, v=0 to N, and N=8.
Orthogonality of the DCT allows division of the two-dimensional DCT into first and second one-dimensional DCTs. More specifically, applying variable v to f(x, y) instead of variable y, intermediate results .phi.(x, v) are found by the following equation (3) indicating the first one-dimensional DCT: ##EQU2##
Then, applying variable u to the intermediate results .phi.(x, v) instead of variable x, the transform values F(u, v) are found by the following equation (4) indicating the second one-dimensional DCT: ##EQU3##
The 8.times.8 transform values F(u, v) found in this way is quantized by dividing them by a quantization coefficient prescribed according to the quantization table 301. In the JPEG, the resultant 8.times.8 transform values F*(u, v) (quantized data) are zigzag scanned to be transformed into a one-dimensional array. FIG. 9 schematically shows the order of the zigzag scanning. The numbers allotted to 8.times.8 squares indicate a sequence of the one-dimensional array.
The one-dimensional array is encoded by Huffman encoding for transforming an object to be coded in accordance with its rate of occurance, allotting a shorter code when the frequency is higher, with non-zero elements and zero run length (the number of consecutive zero elements) as a pair.
The reverse of the encoding is decoding. Reversely following the procedure shown in FIG. 9, the one-dimensional array is decoded by Huffman decoding to be arranged in an 8.times.8 matrix (hereinafter referred to as "inverse zigzag scanning"). If the decoding is perfectly operated, the transform values F*(u, v) can be obtained.
In the inverse quantization, the transform values F*(u, v) are multiplied by the quantization coefficient prescribed according to the quantization table 301 to form restored transform values F**(u, v). In general, there is a quantization error between the transform values F(u, v) and F**(u, v).
The IDCT requires the two-dimensional procedures as well as the DCT, which is expressed as follows: ##EQU4## where the transform value f**(x, y) is a pixel value in the xth row and the yth column of the restored image data of 8.times.8 pixels before postprocessed.
The IDCT allows division of the two-dimensional IDCT into first and second one-dimensional IDCTs as well as the DCT. More specifically, applying variable x to F**(u, v) instead of variable u, intermediate results .PSI.(x, v) are found by the following equation (6) indicating the first one-dimensional IDCT: ##EQU5##
Then, applying variable y to the intermediate result .PSI.(x, v) instead of variable v, the transform value f**(x, y) is found by the second following equation (7) indicating the second one-dimensional IDCT. ##EQU6##
FIGS. 10 through 12 are schematic diagrams showing arrangements of the intermediate results .phi.(x, v). When the first one-dimensional DCT is performed along rows on the pixel values f(x, y) of a matrix shown in FIG. 10 to obtain the intermediate results .phi.(x, v), as is evident from the equation (3), only the pixel values in the xth row, f(x, 0), f(x, 1), . . . , f(x, 7), are required for the DCT. Thus, once the intermediate results .phi.(x, 0), .phi.(x, 1), . . . , (x, 7) are obtained, the pixel values f(x, 0), f(x, 1), . . . , f(x, 7) are no longer needed. From this, the intermediate results .phi.(x, v) can be arranged in the same matrix in place of the pixel values f(x, y) for the second one-dimensional DCT along columns.
FIG. 11 schematically shows that the intermediate results .phi.(0, 0), .phi.(0, 1), . . . , .phi.(0, 7) are obtained from the pixel values in the 0th row, f(0, 0), f(0, 1), . . . , f(0, 7), and are arranged in place of the pixel values f(0, 0), f(0, 1), . . . , f(0, 7).
FIG. 12 further shows that the pixel values f(x, y) in all rows are likewise substituted by the intermediate results .phi.(x, v). Arranged in this way, the intermediate results .phi.(x, v) need to be read out along columns in the second DCT. This is because, as is evident from the equation (4), applying the variable x indicating a row as an adding parameter requires calculation of the sum of products in all rows in the vth column. FIG. 13 schematically shows that the transform values F(0, 0), F(1, 0), . . . , F(7, 0) obtained from the intermediate results .phi.(0, 0), .phi.(1, 0), . . . , .phi.(7, 0) are arranged.
FIG. 14 is a schematic diagram showing how the intermediate results .phi.(x,v) of a matrix as shown in FIG. 12 are stored in a memory space. In the specification, "arrangement" indicates how data is located in a matrix, and "storage" indicates that the data in a matrix is stored at a predetermined address in a memory.
In general, values in a matrix are stored in a memory space along each row. FIG. 14 shows how data is stored in a memory space displayed every hexadecimal 4 bytes when the size of the data is 16 bits, or 2 bytes.
As stored in a memory in this way, in order to obtain the transform values F(u, v), the intermediate results .phi.(x, v) have to be read out every 16 bytes, skipping data in between.
Of course, it might be possible to read all of the intermediate results .phi.(x, v) at a time by processing data in an 8.times.8 block with a customized exclusive memory. However, in a system built up with a generalized processor or memory such as a DRAM, calculation of an address is necessary for making a separate access to data in a memory space in each block of 16 bytes. Thus, it is difficult to read a plurality of the intermediate results .phi.(x, v) all together.
Secondly raised is complication of the zigzag scanning. The order of this scanning cannot be expressed by a simple equation, so that it is previously arranged in a table form within the memory. With reference to the table, an readout address is calculated and the quantized transform values F*(u, v) are read out. The same applies to the decoding. This kind of technique for specifying the order of the scanning with reference to a table has been, for example, introduced in a JPEG program of Independent JPEG Group distributed as a public domain program, or an MPEG1 decoder program of the University of California at Barcley.
When the order of the scanning is specified by such a table, the memory must be refereed to in two stages, first in referring to the table and second in reading out the quantized transform value F*(u, v) at an address specified by the table. This increases processing time. Especially, if there is waiting time in referring to the table, processing time is much more increased. Further, as the zigzag scanning makes an access to discontinuous addresses in a memory space, it is impossible to read a plurality of the quantized transform values F*(u,v) at a time. The same applies to the inverse zigzag scanning.